//The set [1, 2, 3, ..., n] contains a total of n! unique permutations. 
//
// By listing and labeling all of the permutations in order, we get the followin
//g sequence for n = 3: 
//
// 
// "123" 
// "132" 
// "213" 
// "231" 
// "312" 
// "321" 
// 
//
// Given n and k, return the kth permutation sequence. 
//
// 
// Example 1: 
// Input: n = 3, k = 3
//Output: "213"
// Example 2: 
// Input: n = 4, k = 9
//Output: "2314"
// Example 3: 
// Input: n = 3, k = 1
//Output: "123"
// 
// 
// Constraints: 
//
// 
// 1 <= n <= 9 
// 1 <= k <= n! 
// 
// Related Topics 数学 回溯算法 
// 👍 519 👎 0


package leetcode.editor.cn;

//Java：Permutation Sequence
 class P60PermutationSequence {
    public static void main(String[] args) {
        Solution solution = new P60PermutationSequence().new Solution();
        // TO TEST
        solution.getPermutation(3, 3);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        public String getPermutation(int n, int k) {
            int[] arr = new int[n];
            for (int i = 1; i <= arr.length; i++) {
                arr[i - 1] = i;
            }
            return permute(arr, k);
        }

        int count = 0;
        String result;
        boolean[] visited;
        public String permute(int[] nums, int k) {
            visited = new boolean[nums.length];
            permute(nums,  new StringBuilder(), k);
            return result;
        }

        private void permute(int[] nums, StringBuilder sb, int k) {
            if (sb.length() == nums.length) {
                count++;
                if (count == k) {
                    result = sb.toString();
                }
                return;
            }
            for (int i = 0; i < nums.length; i++) {
                if (visited[i] == false) {
                    sb.append(nums[i]);
                    visited[i] = true;
                    permute(nums, sb, k);
                    sb.deleteCharAt(sb.length() - 1);
                    visited[i] = false;
                }

            }
        }


    }
//leetcode submit region end(Prohibit modification and deletion)

}